import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * Created by xiebang
 * Description
 * User:小谢
 * Date:2021-10-26
 * Time:17:00
 */
public class BinarySearchTree {
    //根节点
    public Node root;

    //创建二叉树节点
    class Node{
        public int val;
        public Node left;
        public Node right;

        public Node(int val){
            this.val = val;
            this.left = null;
            this.right = null;
        }

    }
    Queue<Node> queue = new LinkedList<>();

    //查找
    public Node search(int key){
        //从根节点开始遍历
        Node cur = root;
        while (cur != null){
            if (cur.val == key){
                return cur;//
            }else if (cur.val < key){
                cur =cur .right;//小于目标元素就向右子树遍历
            }else {
                cur = cur.left;//大于目标元素就向左子树遍历
            }
        }
        return null;
    }

    //插入
    public void insert(int val){
        Node newNode = new Node(val);
        if (root == null) {
            root = newNode;
        }else {
            Node cur = root;
            Node parent = null;
            while (cur!=null){
                if (cur.val < val){
                    parent = cur;
                    cur = cur.right;
                }else {
                    parent = cur;
                    cur = cur.left;
                }
            }
            if (parent.val > val){
                parent.left = newNode;
            }else {
                parent.right = newNode;
            }
        }
    }

    //删除
    public void remove(int key){

        Node cur = root;
        Node parent = null;
        //先找到该节点
        while (cur != null){
                if(cur.val == key){
                    removeKey(cur,parent);
                }else if (cur.val < key){
                    parent = cur;
                    cur = cur.right;
                }else {
                    parent = cur;
                    cur = cur.left;
                }
        }
    }

    private void removeKey(Node cur, Node parent) {
        //当该节点为左子树为空
        if (cur.left == null){
            if (cur == root){
                root = cur.right;
            }else if (parent.left == cur){
                parent.left = cur.right;
            }else {
                parent.right = cur.right;
            }
        }else if (cur.right == null){
            if (cur == root){
                root = cur.left;
            }else if (parent.left == cur){
                parent.left = cur.left;
            }else {
                parent.right = cur.right;
            }
        }else {
            //当左右子树都不为null时找到左子树的最大值 或者右子树的最小值(本代码找右子树的最大值)
            Node target = cur.right;
            Node targetParent = cur;

            while (target.left != null) {
                targetParent = target;
                target = target.left;
            }
            cur.val = target.val;


            if (targetParent.left == target){
                    targetParent.left = target.right;
                }else {
                targetParent.right = target.right;
            }

        }

    }
    Stack<Node> stack = new Stack<>();
    public void inOrder(Node curroot){
        if (curroot == null){
            return;
        }
        inOrder(curroot.left);
        System.out.print(curroot.val + " ");
        inOrder(curroot.right);
    }

    public void prevOrder(Node curroot){
        if (curroot == null){
            return;
        }
        System.out.print(curroot.val + " ");
        prevOrder(curroot.left);
        prevOrder(curroot.right);
    }
}
